The present invention relates generally to improvements in binary arithmetic mechanisms and more particularly pertains to new and improved division apparatus wherein the quotient of two binary numbers is formed by determining the reciprocal of the divisor and multiplying it by the dividend.
Those concerned with the development of binary arithmetic mechanisms have recognized the need for mechanisms that have redundant structure and are able to perform division as inexpensively and as fast as multiplication. Among the arithmetic operations which are most often implemented in digital computer hardware, division stands out as the most complex to control and costly to execute. For example, refer to: Digital Systems: Hardware Organization and Design, by F. J. Hill and G. R. Peterson, published by John Wylie and Sons, 1973, and Design of a Computer -- The Control Data 6600, by J. E. Thornton, published by Scott-Foresman and Company, Glenview, Illinois, 1970. These text books describe division as taking three to four times as long as multiplication.
With few exceptions, previously employed binary arithmetic algorithms have had strong decimal origins. Although conventional decimal approaches to addition, subtraction and multiplication are well adapted to binary machine implementation, the same cannot be said for "pencil and paper" decimal division nor for Newton-Raphson iterative methods of division. Nevertheless, almost all previously implemented binary division procedures derive from decimal procedures which fall into one or the other of these two categories.
Binary division procedures which do not have strong decimal origins have been reported, for example, by Huei Ling in U.S. Pat. No. 3,633,018, Hugh N. Sierra in U.S. Pat. No. 3,648,038, Goldschmidt and Powers in U.S. Pat. No. 3,508,038 and by W. Scott Bennett in U.S. Pat. No. 3,777,132. The division procedures described in the above patents have one or more relative disadvantages. For example, the method of Goldschmidt and Powers requires a table reference to initiate it and several multiplications to complete it. All the division apparatus described in the above recited publications utilize rather complex non-modular hardware that is largely unique to the division process.